// https://leetcode.cn/problems/spiral-matrix/description/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 模拟螺旋遍历矩阵元素
// 2. 维护四个边界指针控制遍历方向
// 3. 按右→下→左→上顺序循环遍历
// 4. 每次遍历后收缩对应边界
// 5. 时间复杂度：O(m×n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) 
    {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> ret;

        int l = 0, r = n - 1, t = 0, b = m - 1;

        while (true)
        {
            for (int j = l ; j <= r ; j++)
                ret.push_back(matrix[t][j]);
            if (++t > b) break;

            for (int i = t ; i <= b ; i++)
                ret.push_back(matrix[i][r]);
            if (--r < l) break;

            for (int j = r ; j >= l ; j--)
                ret.push_back(matrix[b][j]);
            if (--b < t) break;

            for (int i = b ; i >= t ; i--)
                ret.push_back(matrix[i][l]);
            if (++l > r) break;
        }

        return ret;
    }
};

int main()
{
    vector<vector<int>> matrix1 = {{1,2,3},{4,5,6},{7,8,9}};
    vector<vector<int>> matrix2 = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};

    Solution sol;

    auto v1 = sol.spiralOrder(matrix1);
    auto v2 = sol.spiralOrder(matrix2);

    for (const int& num : v1)
        cout << num << " ";
    cout << endl;

    for (const int& num : v2)
        cout << num << " ";
    cout << endl;

    return 0;
}